# 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
#
#  示例 1：
# 输入：s = "aab"
# 输出：[["a","a","b"],["aa","b"]]
#
#  示例 2：
# 输入：s = "a"
# 输出：[["a"]]
#
#
#  Related Topics 字符串 动态规划 回溯 👍 1772 👎 0
from typing import List


class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n, singel_res, res = len(s), list[str](), list[list[str]]()
        # 先通过动态规划求出 s 的所有子串是否是回文串:
        #   dp[i][j] 表示 s[i:j]是否是回文串
        #   dp[i][j] = dp[i + 1][j - 1] && (s[i] == s[j])
        dp = [[True] * n for _ in range(n)]

        def get_sub_palindromes():
            """
            dp[i][j] 表示 s[i:j]是否是回文串
            dp[i][j] = dp[i + 1][j - 1] && (s[i] == s[j])(含义为子串 s[i+1][j-1]要是回文串并且添加的头尾字符串要相等)
            """
            for i in range(n - 1, -1, -1):
                for j in range(i + 1, n):
                    dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

        def dfs(i: int):
            if i == n:
                res.append(singel_res[:])
                return
            for j in range(i, n):
                if dp[i][j]:
                    singel_res.append(s[i:j + 1])
                    dfs(j + 1)
                    singel_res.pop()

        # 先通过动态规划求出 s 的所有子串是否是回文串
        get_sub_palindromes()
        # 然后回溯获取满足条件的组合
        dfs(0)

        return res


if __name__ == "__main__":
    s = "aab"
    print(Solution().partition(s))
